/**
 * 深度优先实现方式
 */

window.SPACE = 0;

/**
 * 创建一个二维数组，并打乱顺序
 */
function createAry(cols, rows, seeds) {
    if (cols * rows % 2 == 1) cols ++;
    let a = new Array(rows + 2);
    let ans = 0;
    for (let i=0;i<a.length;i++) {
        a[i] = new Array(cols + 2);
        for (let j=0;j<a[i].length;j++) {
            if (i * j == 0 || i == a.length - 1 || j == a[0].length - 1) {
                a[i][j] = SPACE;
            } else {
                a[i][j] = seeds[ans++ % seeds.length];
                let rndx = parseInt(Math.random() * i) + 1;
                let rndy = parseInt(Math.random() * j) + 1;
                let tmp = a[i][j];
                a[i][j] = a[rndx][rndy];
                a[rndx][rndy] = tmp;
            }
        }
    }
    return a;
}

function disappear(a, x0, y0, targetx, targety) {
    if (a[x0][y0] === SPACE || a[targetx][targety] === SPACE
        || a[x0][y0] !== a[targetx][targety]
        || (x0 === targetx && y0 === targety)) {
        return false;
    }
    return bfs(a, x0, y0, targetx, targety, (res)=>{
        if (res) {
            a[x0][y0] = SPACE;
            a[targetx][targety] = SPACE;
        }
    });
}

// 广搜核心算法
function bfs(a, x0, y0, targetx, targety, callback) {
    const directions = [{x:-1,y:0},{x:0,y:-1},{x:1,y:0},{x:0,y:1}];
    let stack = [];
    let flags = {};

    let ans = 0;
    stack.push({x:x0, y:y0, pre:null});
    do {
        for (let i=0;i<directions.length;i++) {
            let oneNode = { x: stack[ans].x + directions[i].x, y: stack[ans].y + directions[i].y, pre: stack[ans] };
            if (flags[oneNode.x + '_' + oneNode.y] || oneNode.x < 0 || oneNode.y < 0
                || oneNode.x >= a.length || oneNode.y >= a[0].length) continue;
            let zCount = 0;
            let p = oneNode;
            while (p.pre) {
                if (p.pre.pre && !(p.pre.pre.x===p.x||p.pre.pre.y===p.y)) {
                    zCount ++;
                }
                p = p.pre;
            }
            if (a[oneNode.x][oneNode.y] === SPACE) {
                if (animateList) { /*此语句仅用于演示模式*/
                    animateList.push({...oneNode, type: '+'});
                }
                if (zCount > 2) continue;
                stack.push(oneNode);
                flags[oneNode.x + '_' + oneNode.y] = true;
            } else if (oneNode.x === targetx && oneNode.y === targety) {
                stack.push(oneNode);
                if (zCount <= 2) {
                    // callback({x1:stack[0].x, y1: stack[0].y, x2: oneNode.x, y2: oneNode.y});
                    callback(true);
                    return oneNode;
                }
            }
        }
    } while (++ans < stack.length);
    return null;
}